The invention relates to data storage devices, and more particularly, to a method and device for storing both large and small files in a data storage device.
One method of storage organization often utilized today involves listing partition information in a File Allocation Table (FAT). A partition is divided up into identically sized storage units. In some FAT systems these storage units are referred to as clusters, which are simply identically sized small blocks of contiguous space. Cluster sizes vary depending on the type of FAT file system being used and the size of the partition, typically cluster sizes lie somewhere between 2 KB and 32 KB. Each file may occupy one or more of these clusters depending on its size; thus, a file is represented by a chain of these clusters (referred to as a singly linked list). However these chains are not necessarily stored adjacently on the disk's surface but are often instead fragmented throughout the Data Region.
FIG. 1 shows a portion of a typical File Allocation Table (FAT) 100 according to the related art. The File Allocation Table (FAT) is a list of entries that map to each cluster on the partition. Each entry records one of five things:                the address of the next cluster in a chain (shown as a numeric entry in FIG. 1)        a special end of file (EOF) character that indicates the end of a chain (shown as the letter ‘E’ in FIG. 1)        a special character to mark a bad cluster (not shown in FIG. 1)        a special character to mark a reserved cluster (not shown in FIG. 1)        a special character to note that that cluster is unused (shown as ‘X’ in FIG. 1)        
Each version of the FAT file system uses a different size for FAT entries. The size is indicated by the name, for example the FAT16 file system uses 16 bits for each entry while the FAT32 file system uses 32 bits. This difference means that the File Allocation Table of a FAT32 system can map a greater number of clusters than FAT16, allowing for larger partition sizes with FAT32. This also allows for more efficient use of space than FAT16, because on the same hard drive a FAT32 table can address smaller cluster which means less wasted space.
In disc-type storage medium such as magnetic based hard disk drive systems and digital video/versatile disc based systems, two major factors impact file access performance: time to access metadata, and time to jump to successive storage units on the disc. Time to access metadata involves the time to process the FAT information to determine where on the disc the desired information is stored. For example, time to access metadata includes the time required to perform seek operations due to the FAT generally being located in an inner area of the disc/disk. When reading data of the file sequentially, this costs time to seek to inner areas of the disc/disk to read the metadata and determine a next storage unit in the chain, and then to seek back to the outer area of the disc/disk to continue reading data of the file. Mechanical operation is time-consuming. Time to jump to successive storage units includes the time required for the mechanical operations of the disc when performing other seek operations and disc rotation when moving from one storage unit to the next storage unit.
When deciding the size of each storage unit (i.e., cluster size), in order to reduce the time required by mechanically moving a pick up head across different areas of the disc, a larger storage unit size is desirable. In this way, more information of each file is read from adjacent data on the storage medium, and throughput is thereby increased. However, the result of a large storage unit size is that some smaller files may not fully fill a storage unit, or may leave a large portion of the last storage unit empty. Such a situation is commonly referred to as internal fragmentation and lowers the storage space efficiency of the storage medium. That is, internal fragmentation is simply wasted space within the storage system. A compromise must therefore be made between small storage size having efficient space utilization and large storage size having high speed data transfer throughput.